package com.cskaoyan.javase.recursion._2hanoi;

/**
 * 汉诺塔（Hanoi）问题，是经典的递归问题，学习递归一般都绕不开它，这里我们就学习一下如何使用递归求解汉诺塔问题。
 *
 * 首先看一下汉诺塔问题的描述：
 * 相传在古印度的圣庙中，有一种被称之为汉诺塔（也叫河内塔，Hanoi）的游戏
 * 简单来说：有三个塔1，2，3，塔1上有 N 个（N>1）穿孔圆盘，大盘在下，小盘在上
 * 要求按下列规则将所有圆盘移至塔3：
 * 	1，每次只能移动一个圆盘
 * 	2，大盘一定在小盘之下
 * 提示：可将圆盘临时置于塔2，也可以将塔1的圆盘重新移回塔1，但都必须遵循上述两条规则
 * 问：当塔1上有N（N>=1）个圆盘时，最少要移动多少次才能完成汉诺塔问题？（注意是最少）
 *
 * 怎么做呢？还是那句话，要往分解的方向去靠，怎么分解汉诺塔问题呢？
 * 实际上汉诺塔问题可以做以下分解：
 *      1.必不可少的一步是，把最大的盘子从塔1到塔3，共需要1步
 *      2.要想实现1中的操作，需要将n-1个盘子从塔1移到塔2
 *      3.完成1中操作后，n-1个盘子都在塔2上，现在只需要将n-1个盘子从塔2移到塔3
 * 设完成n个盘子的汉诺塔问题，至少需要f(n)步
 * 所以f(n)可以做以下分解：
 *      1.把最大的盘子从塔1到塔3，共需要一步
 *      2.需要将n-1个盘子从塔1移到塔2,实际上就是n-1个盘子的汉诺塔问题，需要f（n-1）步
 *      3.只需要将n-1个盘子从塔2移到塔3,实际上就是n-1个盘子的汉诺塔问题，需要f（n-1）步
 * f(n) = f(n-1) + 1 + f(n-1)
 * 但是以上分解不是无限制的
 * 因为当n=1时 f(1) = 1
 *
 * 根据f(n) = f(n-1) + 1 + f(n-1)求f(n)的通项公式
 * f(n) = 2f(n-1) + 1
 * f(n) + 1 = 2f(n-1) + 2
 * f(n) + 1 = 2(f(n-1) + 1)
 * f(n) + 1 / ((f(n-1) + 1)) = 2
 * 所以:
 * f(n) = 2^n - 1
 *
 *
 * @since 17:43
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(hanoi(6));
    }

    // 该方法是求解汉诺塔问题,返回值是n个盘子的汉诺塔问题至少需要的步骤
    public static long hanoi(int n) {
        // 递归的出口
        if (n == 1) {
            return 1;
        }
        return hanoi(n - 1) + 1 + hanoi(n - 1);
    }
}
